package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _111_minDepth {
    public int minDepth(TreeNode root) {
        if(root==null){return 0;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int levels = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            levels++;
            for(int i=0; i<size;i++){
                TreeNode node = queue.poll();
                if(node.left==null && node.right==null){
                    return levels;
                }
                if(node.left!=null){queue.add(node.left);}
                if(node.right!=null){queue.add(node.right);}
            }
        }
        return levels;
    }

    public int minDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = minDepth1(root.left);
        int right = minDepth1(root.right);
        if (root.left == null) {
            return right+1;
        }else if(root.right == null){
            return left+1;
        }else{
            return Math.min(left, right)+1;
        }
    }


}
